package dmsxl.huisu;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/12 22:09
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 *
 * 只使用数字1到9
 * 每个数字 最多使用一次 
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 */
public class hs4_216 {
    static List<List<Integer>> res = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    public static void main(String[] args) {
        res = combinationSum3(3, 7);
        System.out.println(res);
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {
        combineHelper1(k, n, 1, 0);
        return res;
    }

    public static void combineHelper1(int k, int n, int startIndex, int sum){
        if (sum > n){
            return;
        }
        if (path.size() == k){
            if (sum == n){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);
            sum += i;
            combineHelper1(k, n, i+1, sum);
            path.removeLast();
            sum -= i;
        }
    }
}
